package leetcode_jz_offer.day10_dp;

/**
 * 一串数字翻译成字符串多少种翻译方法
 **/
public class Num46_把数字翻译成字符串 {
    //dp[i]=dp[i-1]:因为一个数字一定可以翻译，所以dp[i]的值至少是dp[i-1]
    //dp[i-2]不能组合时，dp[i]=dp[i-1]，可以组合时，dp[i]=dp[i-1]+dp[i-2]
    public int translateNum(int num) {
        //数字转化为字符串，字符串转化为数组
        String s=String.valueOf(num);
        int length=s.length();
        if(length<2){
            //只有一位数或没有数字，返回1或0种方法
            return length;
        }
        char[] charArray=s.toCharArray();
        int[] dp=new int[length];
        dp[0]=1;
        for (int i = 1; i < length; i++) {
            dp[i]=dp[i-1];
            //判断当前位和前一位能否组成10-25的数(dp[i-2]是否存在)
            int n=10*(charArray[i-1]-'0')+(charArray[i]-'0');
            if(n>9&&n<26){
                if(i<2){
                    dp[i]++;
                }else{
                    dp[i]+=dp[i-2];
                }
            }
        }
        //循环完毕，dp数组最后一位即为最终统计值
        return dp[length-1];
    }
}
